package fun.coding.leetcode;

import java.util.LinkedList;
import java.util.Queue;

public class PopulatingNextRightPointersInEachNodeII {

	public static void main(String[] args) {

	}
	
	/*
			    1 -> NULL
			  /  \
			 2 -> 3 -> NULL
			/ \    \
		   4-> 5 -> 7 -> NULL
		   
		   This is iterative solution, still connecting the next level while on current level
		   need to find the next level's head
	 */
	public void connect(TreeLinkNode root) {
		if (root == null) return;
		
		TreeLinkNode cur = root;
		while (cur != null) {
			TreeLinkNode dummy = new TreeLinkNode(-1);
			// Use this dummy node kinda like a linkedList
			TreeLinkNode pre = dummy;
			
			while (cur != null) {
				if (cur.left != null) {
					pre.next = cur.left;
					pre = pre.next;
				}
				
				if (cur.right != null) {
					pre.next = cur.right;
					pre = pre.next;
				}
				
				cur = cur.next;
			}
			cur = dummy.next;
		}
	}
	
	
	// Use one queue will do, but constant space
	public void connectOneQueue(TreeLinkNode root) {
		if (root == null) return;
		
		Queue<TreeLinkNode> q1 = new LinkedList<TreeLinkNode>();
		Queue<TreeLinkNode> q2 = new LinkedList<TreeLinkNode>();
		
		q1.add(root);
		
		while (true) {
			if (q1.isEmpty()) break;
			
			TreeLinkNode pre = q1.peek();
			
			while (!q1.isEmpty()) {
				TreeLinkNode t = q1.poll();
				pre.next = t;
				pre = t;
				
				if (t.left != null) {
					q2.add(t.left);
				}
				if (t.right != null) {
					q2.add(t.right);
				}
			}
			pre.next = null;
			q1 = q2;
			q2 = new LinkedList<TreeLinkNode>();
		}
		
	}
}
